Information constrained and finite-time distributed optimisation algorithms

Abstract

This paper studies the delay-accuracy trade-off for an unconstrained quadratic Network Utility Maximization (NUM) problem, which is solved by a distributed, consensus based, constant step-size, gradient-descent algorithm. Information theoretic tools such as entropy power inequality are used to analyse the convergence rate of the algorithm under quantised inter-agent communication. A finite-time distributed algorithm is proposed to solve the problem under synchronised message passing. For a system with N agents, the algorithm reaches any desired accuracy within 2N iterations, by adjusting the step-size, α. However, if N is quite large or if the agents are constrained by their memory or comput..